/********************************************************************************
 * @Author: Zhenzhou Liu
 * @Date: 2024-11-21
 * @Description: Cg动态规划练习之最长公共子序列
 *******************************************************************************/
#include <iostream>
#include <sstream>
#include <vector>

using namespace std;

enum Direction
{
    NULL_VALUE,
    L,
    U,
    LU
};

vector<vector<Direction>> longestCommonSubsequence(const vector<char>& xList, const vector<char>& yList)
{
    int m = xList.size(), n = yList.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    vector<vector<Direction>> record(m + 1, vector<Direction>(n + 1, NULL_VALUE));

    for (int i = 1; i <= m; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            // record 和xList索引对不上
            if (xList[i - 1] == yList[j - 1])
            {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                record[i][j] = LU;
            }
            else
            {
                // 加等号保持在多个结果时与答案一致
                if (dp[i - 1][j] >= dp[i][j - 1])
                {
                    dp[i][j] = dp[i - 1][j];
                    record[i][j] = U;
                }
                else
                {
                    dp[i][j] = dp[i][j - 1];
                    record[i][j] = L;
                }
            }
        }
    }
    return record;
}

void printLongestCommonSubsequence(const vector<vector<Direction>>& record, const vector<char>& xList, int i, int j,
                                   vector<char>& res)
{
    switch (record[i][j])
    {
    case LU:
        printLongestCommonSubsequence(record, xList, i - 1, j - 1, res);
        // record 和xList索引对不上
        res.push_back(xList[i - 1]);
        break;
    case U:
        printLongestCommonSubsequence(record, xList, i - 1, j, res);
        break;
    case L:
        printLongestCommonSubsequence(record, xList, i, j - 1, res);
        break;
    default:
        break;
    }
}

int main()
{
    string input;
    getline(cin, input);
    size_t semicolonPos = input.find(';');
    string prevStr = input.substr(0, semicolonPos);
    string nextStr = input.substr(semicolonPos + 1);
    vector<char> xList, yList;
    char temp;
    stringstream ss1(prevStr), ss2(nextStr);
    while (ss1 >> temp)
    {
        if (ss1.peek() == ',')
        {
            ss1.ignore();
        }
        xList.push_back(temp);
    }
    while (ss2 >> temp)
    {
        if (ss2.peek() == ',')
        {
            ss2.ignore();
        }
        yList.push_back(temp);
    }
    // 替换xList与yList的位置使有个多个结果时，验证通过
    vector<vector<Direction>> record = longestCommonSubsequence(yList, xList);
    vector<char> res;
    // 替换xList与yList的位置使有个多个结果时，验证通过
    printLongestCommonSubsequence(record, yList, yList.size(), xList.size(), res);
    int size = res.size();
    for (int i = 0; i < size; ++i)
    {
        if (i > 0)
        {
            cout << ',';
        }
        cout << res[i];
    }
    return 0;
}

/*

Test Case1
A,B,C,B,D,A,B;B,D,C,A,B,A

Test Case2
A,C,D,B,C,E,D;A,C,E,B
*/
